Bitap algorithm
BIT-parallel Approximate Pattern matching
Baeza-Yates-Gonnet, shift-and, shift-orとも呼ばれる
曖昧検索にも利用できる
#WIP
レーベンシュタイン距離
割と簡単に再実装できるぽいmrsekut.icon
文字列マッチングを有限オートマトンの受理状態と捉える
ビット演算で有限オートマトンの状態遷移をシミュレートする
/takker/Bitap algorithm
/nishio/Bitapアルゴリズム
https://ja.wikipedia.org/wiki/Bitap%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
Flexible Pattern Matching Strings: Practical On-Line Search Algorithms for Texts and Biological Sequencesに書いてるらしい
https://www.amazon.co.jp/dp/0521039932
https://en.wikipedia.org/wiki/Bitap_algorithm